package leetcode_400;

/**
 *@author 周杨
 *LongestIncreasingPathInAMatrix_329 从2D矩阵中寻找一条最长的递增路径
 *describe:用递归加dp优化算法 AC 30%
 *2018年7月4日 上午10:57:25
 */
public class LongestIncreasingPathInAMatrix_329 {
	int dp[][];
	int res=0;
	int[][] matrix;
	int row,col;
	public static void main(String[] args) {
		System.out.println(-1>>1);

	}
	public int longestIncreasingPath(int[][] matrix) {
	     if(matrix.length==0||matrix[0].length==0)
	    	 return 0;
	     this.matrix=matrix;
	     this.row=matrix.length;
	     this.col=matrix[0].length;
	     this.dp=new int[row][col];
	     int max=1;
	     for(int i=0;i<row;i++)
	    	 for(int j=0;j<col;++j) {
	    		 max=Math.max(max, help(i,j));
	    	 }
	    return max;	 
	}
	
	public int help(int i,int j) {
		int left=1,right=1,up=1,down=1;
		if(i<row-1&&matrix[i][j]<matrix[i+1][j])
			down=dp[i+1][j]==0?1+help(i+1,j):1+dp[i+1][j];
		if(i>0&&matrix[i][j]<matrix[i-1][j])
			up=dp[i-1][j]==0?1+help(i-1,j):1+dp[i-1][j];
		if(j<col-1&&matrix[i][j]<matrix[i][j+1])
			right=dp[i][j+1]==0?1+help(i,j+1):1+dp[i][j+1];
		if(j>0&&matrix[i][j]<matrix[i][j-1])
			left=dp[i][j-1]==0?1+help(i,j-1):1+dp[i][j-1];
		int res=Math.max(Math.max(left, right), Math.max(up, down));
		dp[i][j]=res;
		return res;
	}
}
